#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node
{
    int s;
    int e;
    int p;
    bool operator<(const Node &x) const
    {
        return e < x.e;
    }
};

class Solution
{
private:
protected:
    int GetJobIndex(vector<Node> &node, int cur)
    {
        int l = 0;
        int r = cur;
        int mid = 0;
        while (l < r)
        {
            mid = l + (r - l) / 2;
            if (node[mid].e > node[cur].s)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;
    }

public:
    int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit)
    {
        int n = startTime.size();
        vector<Node> node(n);
        for (int i = 0; i < n; i++)
        {
            node[i].s = startTime[i];
            node[i].e = endTime[i];
            node[i].p = profit[i];
        }
        sort(node.begin(), node.end());
        vector<int> dp(n);
        dp[0] = node[0].p;
        int pre = 0;
        for (int i = 1; i < n; i++)
        {
            pre = GetJobIndex(node, i) - 1;
            dp[i] = pre < 0 ? max(dp[i - 1], node[i].p) : max(dp[pre] + node[i].p, dp[i - 1]);
        }
        return dp[n - 1];
    }
};